package arrAndstr;

import java.util.ArrayList;
import java.util.List;

/*
    28. 找出字符串中第一个匹配项的下标
 */
public class T28 {

    public static void main(String[] args) {

        String haystack = "aaa", needle = "aaaa";
        System.out.println(strStr(haystack, needle));


    }


//    public static int strStr(String haystack, String needle) {
//        return haystack.indexOf(needle);
//    }

    public static int strStr(String haystack, String needle) {
        char chFirst = needle.charAt(0);
        List<Integer> indexList = new ArrayList<Integer>();
        for(int i=0; i<haystack.length(); i++) {
            if(chFirst == haystack.charAt(i)) {
                indexList.add(i);
            }
        }

        int scannedLen = 0;
        for (Integer index : indexList) {
            char chHaystack = haystack.charAt(index);
            char chNeedle = needle.charAt(scannedLen);
            while (chHaystack == chNeedle) {
                scannedLen++;
                if (index+scannedLen >= haystack.length())   break;
                chHaystack = haystack.charAt(index+scannedLen);

                if (scannedLen >= needle.length()) {
                    return index;
                }

                chNeedle = needle.charAt(scannedLen);
            }

            scannedLen = 0;
        }

        return -1;
    }
}
